package graph.unweighted.hamilton;

import java.util.ArrayList;
import java.util.Collections;

import graph.unweighted.CandyGraph;

/**
 * 
 * @Title: HamiltonLoop.java 
 * @Package graph.hamilton 
 * @Description: 求解一个图中的某一个顶点出发是否有哈密尔顿路径
 * @author CandyWall   
 * @date 2021年1月19日 上午11:40:44 
 * @version V1.0
 */
public class CandyHamiltonPath {
    private CandyGraph graph;
    private boolean[] visited;  //记录顶点是否被遍历过，默认都为false
    private int[] pres;    // 记录遍历过程中每一个顶点的上一个顶点
    public CandyHamiltonPath(CandyGraph graph) {
        this.graph = graph;
        visited = new boolean[graph.getVertex_num()];
        pres = new int[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            visited[i] = false;
            pres[i] = -1;
        }
    }
    
    /**
     * 深度优先遍历
     */
    private int dfs(int v, int prev, int left) {
        visited[v] = true;
        pres[v] = prev;
        int lastVertex = -1;
        left--;
        for(int w : graph.adjacentVertexes(v)) {
            if(!visited[w]) {
                lastVertex = dfs(w, v, left);
                if(lastVertex != -1) {
                    return lastVertex;
                }
            }
            // 如果发现已经遍历回到顶点0，并且所有顶点都被访问过了
            // 就表示有哈密尔顿回路
            else if(left == 0) {
                return v;
            }
        }
        visited[v] = false;
        // left++;  搜索失败不需要将left的值还原，left是作为参数传进来的，不影响上一层的left的值
        return lastVertex;
    }
    
    // 判断所有顶点是否都被访问过了
    /*private boolean allVisited() {
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(!visited[v]) {
                return false;
            }
        }
        return true;
    }*/
    // 获取以指定顶点为起始点，看看有没有对应的哈密尔顿路径
    public ArrayList<Integer> getHamiltonPath(int s) {
        ArrayList<Integer> res = new ArrayList<>();
        int cur = dfs(s, 0, graph.getVertex_num());
        if(cur == -1) {
            return res;
        }
        while(cur != s) {
            res.add(cur);
            cur = pres[cur];
        }
        res.add(0);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        CandyGraph graph = new CandyGraph("testData/graph/graph.txt");
        System.out.println(new CandyHamiltonPath(graph).getHamiltonPath(0));
        CandyGraph graph1 = new CandyGraph("testData/graph/hamilton/graph1.txt");
        System.out.println(new CandyHamiltonPath(graph1).getHamiltonPath(0));
        CandyGraph graph2 = new CandyGraph("testData/graph/hamilton/graph2.txt");
        System.out.println(new CandyHamiltonPath(graph2).getHamiltonPath(0));
        CandyGraph graph3 = new CandyGraph("testData/graph/hamilton/graph3.txt");
        System.out.println(new CandyHamiltonPath(graph3).getHamiltonPath(0));
        CandyGraph graph4 = new CandyGraph("testData/graph/hamilton/graph4.txt");
        System.out.println(new CandyHamiltonPath(graph4).getHamiltonPath(2));
    }
}
